#include<iostream>
#include<vector>
using namespace std;

vector<int> searchRange(vector<int> &nums, int target)
{
    // 处理特殊情况，空数组
    if (nums.empty())
    {
        return {-1, -1};
    }
    int left = 0, right = nums.size() - 1;
    int mid = 0;
    int begin = 0;

    // 查找区间的左端点
    // 细节点一：这里只能左指针小于右指针，不能等于
    while (left < right)
    {
        // 细节点二：获取中间值这里不能加一
        mid = left + (right - left) / 2;

        if (nums[mid] < target)
        {
            left = mid + 1;
        }
 
        if (nums[mid] >= target)
        {
            right = mid;
        }
    }

    // 查找左端点结束后，找到继续查找右端点，否则返回没有找到
    if (left == right && nums[left] == target)
    {
        begin = left;
    }
    else
    {
        return {-1, -1};
    }

    right = nums.size() - 1;

    // 查找区间的右端点
    // 细节点一
    while (left < right)
    {
        // 细节点二：获取中间值这里要加一
        mid = left + (right - left + 1) / 2;

        if (nums[mid] <= target)
        {
            left = mid;
        }

        if (nums[mid] > target)
        {
            right = mid - 1;
        }
    }

    return {begin, right};
}

int main()
{
    int target = 8;
    vector<int> nums = {5, 7, 7, 8, 8, 10};

    vector<int> ret = searchRange(nums, target);

    for (auto e : ret)
    {
        cout << e << " ";
    }
    return 0;
}